package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.BuildUtil;

import java.util.ArrayList;
import java.util.List;

public class code120_三角形最小路径和 {

    public static void main(String[] args) {
        List<List<Integer>> listList = new ArrayList<>();
        int[][] ints = new int[][]{
                {2},
                {3, 4},
                {6, 5, 7},
                {4, 1, 8, 3}
        };
        for (int a = 0; a < ints.length; a++) {
            listList.add(BuildUtil.createIntegerList(ints[a]));
        }
        new code120_三角形最小路径和().minimumTotal2(
                listList
        );
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.get(0).size() == 0) {
            return 0;
        }
        for (int a = 1; a < triangle.size(); a++) {
            for (int b = 0; b < triangle.get(a).size(); b++) {
                if (b == 0) {
                    int index = triangle.get(a).get(b);
                    triangle.get(a).set(b, triangle.get(a - 1).get(b) + index);
                } else if (b == triangle.get(a).size() - 1) {
                    int index = triangle.get(a).get(b);
                    triangle.get(a).set(b, triangle.get(a - 1).get(b - 1) + index);
                } else {
                    int index = triangle.get(a).get(b);
                    triangle.get(a).set(b, Math.min(triangle.get(a - 1).get(b) + index,
                            triangle.get(a - 1).get(b - 1) + index));
                }
            }
        }
        int length = triangle.size();
        int min = Integer.MAX_VALUE;
        for (int a = 0; a < triangle.get(length - 1).size(); a++) {
            min = Math.min(triangle.get(length - 1).get(a), min);
        }
        return min;
    }

    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int[] dp = new int[triangle.size()];
        int size = triangle.size();
        for (int j = 0; j < size; j++) {
            dp[j] = triangle.get(size - 1).get(j);
        }
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}
